package com.cn.algorithm01;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/13 19:20
 * 两个链表看成是数字进行相加
 *
 * // 测试链接：https://leetcode.com/problems/add-two-numbers/
 */
public class Code11_AddTwoNumber {
    // 单链表
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        int len1 = listLength(head1);
        int len2 = listLength(head2);
        ListNode l = len1 > len2 ? head1 : head2;
        ListNode curL = l;
        ListNode curS = l == head1 ? head2 : head1;

        ListNode last = curL;//跟踪当前计算位置
        int carry = 0;//进位标志
        int curNum = 0;//当前位置和

        // 短的链表节点不为空
        while (curS != null) {
            curNum = curL.val + curS.val + carry;
            curL.val = (curNum%10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
            curS = curL.next;
        }
        // 长的链表结构不为空
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            last =  curL;
            curL = curL.next;
        }
        // 判断进位是否为1
        if (carry != 0) {
            last.next = new ListNode(1);
        }

        return l;
    }

    public static void main(String[] args) {
        String s = new String("123");
        String t = s;//地址引用，结果为true
        System.out.println(s == t);
    }

    // 求链表长度
    public static int listLength(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }

}
